package likouJava;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //长度小于3直接返回
        if (nums == null || nums.length < 3) {
            return result;
        }
        Arrays.sort(nums);
        int n =nums.length;
        for(int first = 0; first < n; first++){
            if(first > 0 && nums[first] == nums[first - 1]){
                continue;
            }
            //获得第一个数的相反值
            int third = n - 1;
            int target = -nums[first];

            for (int second = first + 1;second < n;second++){
                //确保和上一个数不一样
                if(second > first + 1 && nums[second] == nums[second - 1]){
                    continue;
                }
                //第三个数(右指针)左移
                while(second<third && nums[second] + nums[third] > target){
                    --third;
                }
                if(second == third){
                    break;
                }
                if(nums[second] + nums[third] == target){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    result.add(list);
                }
            }

        }
        return result;
    }

}
